On the Min-Max-Delay Problem: NP-completeness, Algorithm, and Int-Gap

摘要

We study a flow problem where a source streams information to a sink over adirected graph G=(V;E) possibly using multiple paths to minimize the maximumend-to-end delay, denoted as Min-Max-Delay problem. Different from the maximumlatency problem, our setting is unique in that communication over an edgeincurs a constant delay within an associated capacity. We prove thatMin-Max-Delay is weakly NP-complete, and demonstrate that it becomes stronglyNP-complete if we require integer flow solution. We propose an optimalpseudo-polynomial time algorithm for Min-Max-Delay. Moreover, we propose afully polynomial time approximation scheme. Besides, in this paper we observethat the optimal Min-Max-Delay flow can only be achieved by fractional flowsolution in some problem instances and in the worst case the Int-Gap, which isdefined as the maximum delay gap between the optimal integer Min-Max-Delay flowand the optimal Min-Max-Delay flow, can be infinitely large. We also propose anear-tight bi-criteria bound for the Int-Gap. In the end, we show how theresults introduced in this paper can be extended to the multi-commodityMin-Max-Delay problem case.